use std::{cmp::{Ordering, Reverse}, collections::BinaryHeap, u32};

const CHOICES: [u32;8] = [1, 2, 5, 10, 20, 30, 50, 100]; 

/// 在数组[`arr`]中找到第一个不大于[`target`]的元素的索引
fn find_first_not_greater(arr: &[u32], target: u32) -> Option<usize> {
    let mut left = 0;
    let mut right = arr.len();

    while left < right {
        let mid = left + (right - left) / 2;

        if arr[mid] <= target {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    if left > 0 && arr[left - 1] <= target {
        Some(left - 1)
    } else {
        None
    }
}

/// 搜索树的节点
#[derive(Eq, PartialEq)]
struct Node {
    upper_bound: u32, // 次数的预测上界
    count:u32,  // 已经用掉的纸币次数
    reduced_amount: u32, // 剩下的余额
}

// 实现 Ord 特性，根据 count 字段进行比较
impl Ord for Node {
    fn cmp(&self, other: &Self) -> Ordering {
        // 比较 upper_bound 字段，如果 upper_bound 相同，再比较 reduced_amount
        self.upper_bound.cmp(&other.upper_bound)
            .then_with(|| self.reduced_amount.cmp(&other.reduced_amount))
    }
}

impl PartialOrd for Node {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}


fn search(amount: u32) -> Option<u32>{
    // 分支限界法

    // 使用一个最小堆，堆顶存放搜索树中预期上界最小的节点
    let mut heap: BinaryHeap<Reverse<Node>> = BinaryHeap::new();
    heap.push(
        Reverse(Node {
            upper_bound: amount,
            count: 0,
            reduced_amount: amount,
        })
    );
    while !heap.is_empty() {
        let node = heap.pop().unwrap().0;
        let idx = find_first_not_greater(&CHOICES, node.reduced_amount).unwrap();

        // 从可用的最大面值币的种开始迭代
        for i in (0..=idx).rev() {
            let value = CHOICES[i];
            // 计算凑出 reduced_amount 需要的纸币次数上界，并更新 upper_bound
            let upper_bound = node.count + node.reduced_amount.div_ceil(value);
            // 计算剩下的金额
            let reduced_amount = node.reduced_amount % value;

            heap.push(
                Reverse(Node {
                    upper_bound,
                    count: node.count + node.reduced_amount / value,
                    reduced_amount,
                })
            );
        }

        if !heap.is_empty() {
            let peek = heap.peek().unwrap();
            if (&(peek.0)).reduced_amount == 0 {
                // 节点存储的count就是需要的次数
                return Some((&(peek.0)).count);
            }
        }
    }

    // 一般不会到这里来
    return None
}

pub fn dp_rec_mc(amount: u32) -> u32 {
    if amount == 0 {
        0
    }
    else {
        search(amount).unwrap()
    }
}
